package main

type point struct {
	x, y int
}

// 自己写的
func getMaximumGold(grid [][]int) int {
	// (1). 定义所需变量
	var ans, n, m = 0, len(grid), len(grid[0])
	dir := [][]int{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}
	used := make([][]bool, n)
	for i := 0; i < n; i++ {
		used[i] = make([]bool, m)
	}
	// (2). 定义递归函数
	var dfs func(total int, p point)
	dfs = func(total int, p point) {
		// 3. 终止条件， 如果出界，或者碰到 0, 或者是遍历过的
		if p.x == n || p.x == -1 ||
			p.y == m || p.y == -1 || grid[p.x][p.y] == 0 {
			ans = max(ans, total)
			return
		}
		if used[p.x][p.y] == true {
			return
		}
		// 1. 加上当前的 黄金值
		total += grid[p.x][p.y]
		used[p.x][p.y] = true
		// 2. 开始循环
		for _, ac := range dir {
			x := p.x + ac[0]
			y := p.y + ac[1]
			dfs(total, point{x, y})
		}
		// 3.回溯
		used[p.x][p.y] = false
	}

	// (3). 执行，每个有黄金的都可以作为起点
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] != 0 {
				dfs(0, point{i, j})
			}
		}
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// 官方题解， 处理的更好， 上面我是想出界判断一次黄金量，出界写到循环外面，效率要低很多
var dirs = []struct{ x, y int }{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func getMaximumGold(grid [][]int) (ans int) {
	var dfs func(x, y, gold int)
	dfs = func(x, y, gold int) {
		gold += grid[x][y]
		if gold > ans {
			ans = gold
		}

		rec := grid[x][y]
		grid[x][y] = 0
		for _, d := range dirs {
			nx, ny := x+d.x, y+d.y
			if 0 <= nx && nx < len(grid) && 0 <= ny && ny < len(grid[nx]) && grid[nx][ny] > 0 {
				dfs(nx, ny, gold)
			}
		}
		grid[x][y] = rec
	}

	for i, row := range grid {
		for j, gold := range row {
			if gold > 0 {
				dfs(i, j, 0)
			}
		}
	}
	return
}
